package solution._0030._0032;

import java.util.Stack;

/**
 * Created by chen_snow
 * Date: 2021/5/19 22:03
 * Description: 最长有效括号
 */
public class Solution {

    public int longestValidParentheses(String s) {
        Stack<Integer> data = new Stack<>();
        int max = 0;
        // 第一个不被匹配的）
        data.push(-1);

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);

            if (ch == '(') {
                data.push(i);
            } else {
                data.pop();
                if (!data.isEmpty()) {
                    max = Math.max(max, i - data.peek());
                } else {
                    data.push(i);
                }
            }
        }

        return max;
    }

    public int longestValidParentheses1(String s) {

        Stack<Integer> data = new Stack<>();
        int[] flags = new int[s.length()];

        for (int i = 0; i < s.length(); i++) {
            flags[i] = 0;
        }

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);

            if (ch == '(') {
                data.push(i);
            } else {
                if (!data.isEmpty()) {
                    flags[i] = 1;
                    flags[data.pop()] = 1;
                }
            }
        }

        return findMaxIndex(flags);
    }

    public int findMaxIndex(int[] data) {
        int index = -1;
        int max = 0;
        boolean isFind = false;

        for (int i = 0; i < data.length; i++) {
            if (!isFind) {
                if (data[i] == 1) {
                    index = i;
                    isFind = true;
                } else {
                    continue;
                }
            } else {
                if (data[i] == 0) {
                    max = Math.max(max, i - index);
                    isFind = false;
                } else {
                    continue;
                }
            }
        }

        if (isFind) {
            max = Math.max(max, data.length - index);
        }
        return max;
    }
}
